#include <iostream>
#include <vector>

#define PROCESSNUM 5
#define SOURCENUM  3

std::vector<int> Available;
std::vector<int> Work;
std::vector<std::vector<int>> Max;
std::vector<std::vector<int>> Allocation;
std::vector<std::vector<int>> Need;
std::vector<bool> Check;
std::vector<int> Sequence;
std::vector<std::vector<int>> SequenceArray;

void init() {
    srand(time(nullptr));
    Check.resize(5, false);
    // 初始化资
    for (int i = 0; i < SOURCENUM; i++) {
        int num = rand() % 10 + 1;
        Available.push_back(num);
    }
    // 初始化最大需求矩阵
    for (int i = 0; i  < PROCESSNUM; i++) {
        std::vector<int> needed;
        for (int j = 0; j < SOURCENUM; j++) {
            int num = rand() % Available[j] + 1;
            needed.push_back(num);
        }
        Max.emplace_back(needed);
    }
    
    std::vector<int> tmp_ava(Available);
    
    for (int i = 0; i < PROCESSNUM; i++) {
        std::vector<int> alloc;
        // 对当前资源进行分配，有50%的几率为0
        // 也有50%的记录1~Max[i][j]，前提是有资源的前提下
        // 所以对于剩下的50%几率为1~min(Max[i][j], tmp_ava[j])
        // 最后tmp_ava[j]还要减去分配出去的
        for (int j = 0; j < SOURCENUM; j++) {
            bool iszero = rand() % 2;
            if (iszero || tmp_ava[j] == 0) {
                alloc.push_back(0);
            } else {
                int num = 1 + rand() % std::min(Max[i][j], tmp_ava[j]);
                tmp_ava[j] -= num;
                alloc.push_back(num);
            }
        }
        Allocation.emplace_back(alloc);
    }

    Work = tmp_ava;

    for (int i = 0; i < PROCESSNUM; i++) {
        std::vector<int> needed;
        for (int j = 0; j < SOURCENUM; j++) 
            needed.push_back(Max[i][j] - Allocation[i][j]);
        Need.emplace_back(needed);
    }
}

void printInfo() {
    std::cout << "Initial available:" << std::endl;
    for (auto& num : Available)
        std::cout << num << " ";
    std::cout << "\n" << std::endl;
    
    std::cout << "Max:" << std::endl;
    for (int i = 0; i < PROCESSNUM; i++) {
        std::cout << "p" << i << ": ";
        for (auto& num : Max[i])
            std::cout << num << " ";
        std::cout << "\n";
    }
    std::cout << std::endl;

    std::cout << "Allocated:" << std::endl;
    for (int i = 0; i < PROCESSNUM; i++) {
        std::cout << "p" << i << ": ";
        for (auto& num : Allocation[i])
            std::cout << num << " ";
        std::cout << "\n";
    }
    std::cout << std::endl;

    std::cout << "Available:" << std::endl;
    for (auto& num : Work) 
        std::cout << num << " ";
    std::cout << "\n" << std::endl;

    std::cout << "Work:" << std::endl;
    for (auto& num : Work) 
        std::cout << num << " ";
    std::cout << "\n" << std::endl;
    
    std::cout << "Needed:" << std::endl;
    for (int i = 0; i < PROCESSNUM; i++) {
        std::cout << "p" << i << ": ";
        for (auto& num : Need[i])
            std::cout << num << " ";
        std::cout << "\n";
    }
    std::cout << std::endl;    
}

bool isAlloc(int i) {
    for (int j = 0; j < SOURCENUM; j++)
        if (Need[i][j] > Work[j])
            return false;
    return true;
}

bool success = false;

// void dfs() {
//     if (Work == Available) {
//         success = true;
//         return;
//     }

//     for (int i = 0; i < PROCESSNUM; i++) {
//         if (Check[i]) continue;
//         // 判断当前是否可以分配
//         if (isAlloc(i)) {
//             // 当前可以分配
//             // 还要将进程占用的资源还回去
//             Check[i] = true;
//             for (int j = 0; j < SOURCENUM; j++)
//                 Work[j] += Allocation[i][j];
//             Sequence.push_back(i);
//             // 继续向下进行
//             dfs();

//             Sequence.pop_back();
//             Check[i] = false;
//             for (int j = 0; j < SOURCENUM; j++)
//                 Work[j] -= Allocation[i][j];            
//         }
//     }
// }

bool isDepth() {
    for (auto check : Check)
        if (check == false)
            return false;
    return true;
}

bool dfs() {
    // 当资源全都回来之后且搜索深度达到，并且全都为true
    if (Work == Available && isDepth()) {
        success = true;
        return true;
    }
    for (int i = 0; i < PROCESSNUM; i++) {
        if (Check[i]) continue;
        if (isAlloc(i)) {
            Check[i] = true;
            for (int j = 0; j < SOURCENUM; j++)
                Work[j] += Allocation[i][j];
            Sequence.push_back(i);
            SequenceArray.push_back(Work);
            if (dfs()) 
                return true;
            SequenceArray.pop_back();
            Sequence.pop_back();
            Check[i] = false;
            for (int j = 0; j < SOURCENUM; j++)
                Work[j] -= Allocation[i][j];
        }
    }
    return false;    
}

void outSequence() {
    std::cout << "Safe Sequence: ";
    for (auto num : Sequence)
        std::cout << "p" << num << " ";
    std::cout << "\n";

    printf("\tWork\n");
    for (int i = 0; i < PROCESSNUM; i++) {
        std::cout << "p" << Sequence[i] << "\t";
        for (auto num : SequenceArray[i])
            std::cout << num << " ";
        std::cout << "\n";
    }
}

void BankerAlgorithm() {
    // 先测试安全不安全
    // 深度搜索算法
    dfs();
    if (success) {
        outSequence();
        // 根据当前的序列
    } else
        std::cout << "false" << std::endl;
}

int main() {
    init();
    printInfo();
    BankerAlgorithm();
    return 0;
}